/* (c) Copyright 1993 by Joseph Felsenstein.
   Written by Joseph Felsenstein, Akiko Fuseki, Sean Lamont, and Andrew Keeffe.
   Permission is granted to copy and use this program provided no fee is
   charged for it and provided that this copyright notice is not removed. */

#include <map>
#include <string>
#include <vector>
#include "digest.h"
#include "matrix.h"
#include "md4.h"

namespace kitsch_tree
{

	
//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	struct t_kitsch_node
		
//
enum eCHILD_NUM{CHILD_LEFT, CHILD_RITE, CHILD__ALL};
struct t_kitsch_tree;
struct t_kitsch_node
{		  /* describes a leaf sequence or an internal branch node */
	t_kitsch_node(unsigned count, t_kitsch_tree* tree_) :
						tree(tree_),
						index(0),
						treepos(0),
						leaf(false),
						len_to_leaf(0.0),
						same_len_to_leaf(false),
						weight(0.0),
						processed(false),
						parent(0),
						child_num(CHILD_LEFT)
	{
		clear();
	}
	void			clear ()				{	parent = child[0]  = child[1] = 0;}
	t_kitsch_tree*	tree;
	unsigned		index;				// offset into matrix and weights
	unsigned		treepos;			// offset into matrix and weights
	bool			leaf;
	double			len_to_leaf;
	bool			same_len_to_leaf;	// bookkeeps scrunched nodes
	double			weight;				// weight of t_kitsch_node used by scrunch
	bool			processed;			// used by evaluate
	t_kitsch_node *	parent;				// same as phylip back for tips and main nodes
	t_kitsch_node *	child[2];			// same as phylip next->back for main nodes
										// same as phylip next->next->back for main nodes
	eCHILD_NUM		child_num;			// whether is left right or nth child of parent
	
	
	void			CHECK_LINKS() const;
	t_kitsch_node*	sibling() const;
	void			set_parent(t_kitsch_node* new_parent, eCHILD_NUM num);
	void			left_splice_below(t_kitsch_node& new_parent, t_kitsch_node& new_tip);
	t_kitsch_node& 	operator = (const t_kitsch_node& other);
	bool 			operator!= (const t_kitsch_node& other) const;
	bool 			operator== (const t_kitsch_node& other) const;
};

//

//	struct t_kitsch_node
		
//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888


//	t_kitsch_tree
//	=============


//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct t_kitsch_tree
{
	//initialize
	t_kitsch_tree(	t_matrix&							d,
					t_matrix&  							w,
					const std::vector<std::string>&		names,
					double								power,
					t_progress_indicator& 				dots,
					unsigned							cnt_seq_ = 0);
	t_kitsch_tree(	t_kitsch_tree other, t_kitsch_node& from_node);
	void			replace_subtree(t_kitsch_tree other, t_kitsch_node& from_node);
	t_kitsch_tree& 	operator = (const t_kitsch_tree& other);
	void			prepare_data();				
	
	
	t_matrix&							d;
	t_matrix&							w;
	const std::vector<std::string>&		names;
	double								power;
	unsigned 							cnt_seq;
	unsigned 							cnt_nodes;
	unsigned							cnt_trees_examined;
	unsigned							cnt_non_null_data;
	std::vector<t_kitsch_node>			shared_mem;
	std::deque<t_kitsch_node*> 			nodes;
	
	double								sum_sqrs;
	t_kitsch_node*						optimal_add_locus;
	bool								sum_sqrs_lowered;
	
	double								best_sum_sqrs;
	t_progress_indicator*				pdots;
	t_kitsch_node*						root;
	std::map<t_digest, double>			cached_evaluate_results;
	unsigned							cnt_evaluate_cache_hits;
	
	
	void 			CHECK_LINKS() const;
	double			secondtraverse(							t_kitsch_node& ll,
															t_kitsch_node& kk,
															t_kitsch_node& ii,
															t_kitsch_node& jj);
	double			firstraverse(							t_kitsch_node& q,
															t_kitsch_node& r);
	double			sumtraverse(							t_kitsch_node& q);
	void			evaluate();
	void			try_add(								t_kitsch_node& where,
															t_kitsch_node& item,
															t_kitsch_node*& parent);
	void			recursive_find_optimal_add_locus(		t_kitsch_node& where,
															t_kitsch_node& item,
															t_kitsch_node* parent);
	void			get_optimal_add_locus(					t_kitsch_node& item,
															t_kitsch_node* parent);
	void			try_rearrange(							t_kitsch_node& item);
	void			recursive_find_optimal_rearrangement(	t_kitsch_node& item);
	t_kitsch_node*	remove(									t_kitsch_node& item);
	void			rearrange();
	void			maketree(const std::vector<unsigned>& order_of_entry);
	std::string		to_str();
	t_digest&		to_md4_hash(t_digest& hv){return md4_hash(to_str(), hv);}
	// defaults to root
	template <typename T> void for_each(T& t, t_kitsch_node* = 0 );
	template <typename T> void for_each(T& t, const t_kitsch_node* = 0) const;
	template <typename T> void recurse(T& t, t_kitsch_node&);
	template <typename T> void recurse(T& t, const t_kitsch_node&) const;
};


//________________________________________________________________________________________

//	for_each

//________________________________________________________________________________________
template <typename T> void t_kitsch_tree::for_each(T& t, t_kitsch_node* from_node)
{
	t_kitsch_node* p_node = from_node ? from_node : root;
	recurse(t, *p_node);
}

template <typename T> void t_kitsch_tree::for_each(T& t, const t_kitsch_node* from_node) const
{
	const t_kitsch_node* p_node = from_node ? from_node : root;
	recurse(t, *p_node);
}


template <typename T> void t_kitsch_tree::recurse(T& t, const t_kitsch_node& curr_node) const
{
	t.pre_curse(curr_node);
	if (!curr_node.leaf)
	{
		recurse(t, *curr_node.child[CHILD_RITE]);
		recurse(t, *curr_node.child[CHILD_LEFT]);
	}
	t.post_curse(curr_node);
}

template <typename T> void t_kitsch_tree::recurse(T& t, t_kitsch_node& curr_node)
{
	t.pre_curse(curr_node);
	if (!curr_node.leaf)
	{
		recurse(t, *curr_node.child[CHILD_RITE]);
		recurse(t, *curr_node.child[CHILD_LEFT]);
	}
	t.post_curse(curr_node);
}

}

